/* 
 * File:   Basic_Knot.h
 * Author: vicror
 *
 * Created on October 22, 2011, 7:43 PM
  *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files
 * (the "Software"), to deal in the Software without restriction,
 * including without limitation the rights to use, copy, modify, merge,
 * publish, distribute, sublicense, and/or sell copies of the Software,
 * and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#ifndef BASIC_KNOT_H
#define	BASIC_KNOT_H
#include <vector>
#include <algorithm>
namespace SearchEnginer {
    using std::vector;
    template <typename T>
    class Basic_Knot {
    public:
        typedef vector<T> ListItemT;
        typedef typename ListItemT::const_iterator ListItemTConstIter;
        typedef typename ListItemT::iterator ListItemTItr;
    protected:
        ListItemT listItem;
    public:

        /**
         * @brief Конструктор узла
         * @param Нет параметров.
         * @return Нет возврашаемого значения.
         */
        Basic_Knot() {
            clear();
        }

        /**
         * @brief Конструктор копирования узла
         * @param orig - источник копирования.
         * @return Нет возврашаемого значения
         */
        Basic_Knot(const Basic_Knot& orig) {
            copy(orig);
        }

        /**
         * @brief деструктор узла
         * @param Нет параметров.
         * @return Нет возврашаемого значения.
         */
        virtual ~Basic_Knot() {
            clear();
        }

        /**
         * @brief Добавляет узел в список
         * @param orig - Добавляемый узел
         * @return Возрашает количество узлов в списке.
         *
         * Добавляет к списку узлов 1 элемент, если такой элемент
         * не содержится в списке.
         */
        int append(const T& orig) {
            if (!hasItem(orig)) {
                listItem.push_back(orig);
                std::sort(listItem.begin(), listItem.end());
            }
            return listItem.size();
        }

        /**
         * @brief Объединяет 2 списка.
         * @param orig - добавляемый список узлов
         * @return Возрашает количество узлов в списке.
         *
         * Объединяет текуший список узлов с другим списком. При этом
         * дублируюшие узлы будут записаны только один раз.
         */
        int append(const Basic_Knot& orig) {
            ListItemT temp;
            temp.reserve(listItem.size() + orig.listItem.size());
            ListItemTConstIter ghost = orig.listItem.begin();
            ListItemTConstIter home = listItem.begin();
            while (home != listItem.end() && ghost != orig.listItem.end()) {
                if ((*home) == (*ghost)) {
                    temp.push_back(*home);
                    ++ghost;
                    ++home;
                } else {
                    if ((*home) > (*ghost)) {
                        temp.push_back(*ghost);
                        ++ghost;
                    } else {
                        temp.push_back(*home);
                        ++home;
                    }
                }
            }
            while (home != listItem.end()) {
                temp.push_back(*home);
                ++home;
            }
            while (ghost != orig.listItem.end()) {
                temp.push_back(*ghost);
                ++ghost;
            }
            listItem.clear();
            listItem.reserve(temp.size());
            listItem = temp;
            return listItem.size();
       }

        /**
         * @brief Копирует внешний список
         * @param orig - внешний список.
         * @return Нет возврашаемого значения.
         */
        void copy(const Basic_Knot& orig) {
             listItem.clear();
             listItem.resize(orig.listItem.size());
             listItem = orig.listItem;
        }

        /**
         * @brief Находится ли узел в списке
         * @param orig - Искомый узел
         * @return Возрашает true, если узел содержится в списке.
         */
        bool hasItem(const T& orig) const {
            return search(orig) >=0;
        }

        /**
         * @brief Копирует внешний список
         * @param orig - внешний список.
         * @return Возврашет ссылку на список.
         */
        Basic_Knot &operator=(const Basic_Knot& orig) {
            if (&orig != this) {
                copy(orig);
            }
            return *this;
        }


        /**
         * @brief Стирает все элементы из списка
         * @param Нет параметров вызова
         * @return Нет возврашаемого значения
         */
        void clear(void) {
            listItem.clear();
        }

        /**
         * @brief Удаляет элемент из списка.
         * @param orig - Удаляемый элемент
         * @return Нет возврашаемого значения
         */
        void remove(const T& orig){
            int res = search(orig);
            if (res >=0) {
                ListItemTItr itr = listItem.begin() + res;
                listItem.erase(itr);
            }

        }

        /**
         * @brief Возрашает количество элементов в списке
         * @param Нет параметров вызова
         * @return Колличество элементов в списке.
         */
        int size(void) {
            return listItem.size();
        }

        /**
         * @brief Возврашает список элементов
         * @param Нет параметров вызова
         * @return Список элементов.
         */
        ListItemT getItems(void) const {
            return listItem;
        }

        /**
         * @brief Возврашает константный итерртатор на эллемент,
         * соответствуюший значению.
         * @param orig - искомое значение
         * @return Констаннтный итерратор на эдемент в списке.
         */
        ListItemTConstIter getSearchItr(const T& orig) const {
            int ind = search(orig);
            if (ind == -1) {
                return listItem.end();
            } else {
                return listItem.begin() + ind;
            }
        }

        /**
         * @brief Возврашает итерртатор на эллемент,
         * соответствуюший значению.
         * @param orig - искомое значение
         * @return Итерратор на эдемент в списке.
         */
        ListItemTItr getSearchItr(const T& orig) {
            int ind = search(orig);
            if (ind == -1) {
                return listItem.end();
            } else {
                return listItem.begin() + ind;
            }
        }

        /**
         * @brief Возврашает константный итерратор на конец списка
         * @param Нет входных параметров
         * @return Константный итерратор на конец списка
         */

        ListItemTConstIter end(void) const {
            return listItem.end();
        }

        /**
         * @brief Возврашает итерратор на конец списка
         * @param Нет входных параметров
         * @return Итерратор на конец списка
         */

        ListItemTItr end(void)  {
            return listItem.end();
        }

        /**
         * @brief Возврашает ссылку на элемент списка
         * @param orig - индекс элемента
         * @return Ссылка на элемент списка
         */

        T& at(unsigned int index) {
            return listItem.at(index);
        }

    protected:
        /**
         * @brief Находит индекс в списке, которому соответствует элемент.
         * @param orig - искомый элемент.
         * @return Возврашает индекс элемента. В случае неудачи, возврашает -1.
         */
        int search(const T& orig) const {
            bool res = false;
            int middle = -1;
            int end = listItem.size() - 1;
            if (end >= 0) {
                int begin=0;
                if (listItem[end] == orig) {
                    res = true;
                    middle = end;
                } else {
                    bool flag = true;
                    do {
                        middle= (begin+end)/2;
                        flag = middle != begin;
                        if (listItem[middle] == orig) res = true;
                        else {
                            if (listItem[middle] > orig) {
                                end = middle;
                            } else {
                                begin = middle;
                            }
                        }
                    } while (!res && flag);
                }
            }
            if (!res) {
                middle = -1;
            }
            return middle;

        }

        

    };
}



#endif	/* BASIC_KNOT_H */

